0% completed
Problem Statement
Given an array of points in the X-Y plane points where points[i] = [xi, yi], return the minimum area of a rectangle formed from these points. The sides of the rectangle should be parallel to the X and Y axes. If there is not any such rectangle, return 0.
Examples
-
Example 1:
- Input:: points =
[[1,2],[2,1],[1,0],[0,1]] - Expected Output::
0 - Justification:: There are no four points that can form a rectangle with sides parallel to the axes, so the minimum area is 0.
- Input:: points =
-
Example 2:
- :Input:: points =
[[0,1],[0,3],[3,1],[3,3],[4,1],[4,3]] - :Expected Output::
2 - :Justification:: These points form a rectangle with corners at
[3,1],[4,1],[4,3], and[3,3]. This rectangle's area is 2, making it the smallest possible area from these points.
- :Input:: points =
-
Example 3:
- :Input:: points =
[[1,1],[2,2],[3,3]] - :Expected Output::
0 - :Justification:: There are no four points that can form a rectangle with sides parallel to the axes, so the minimum area is 0.
- :Input:: points =
Solution
To solve this problem, we will use a hash set to efficiently check whether a pair of points that could form the opposite corners of a rectangle exist. The core idea is to iterate through all possible pairs of points and use these as potential opposite corners of a rectangle. For each pair, we check if the other two corners (which complete the rectangle) are present in our set of points. This approach works well because checking for the existence of a point in a hash set is an O(1) operation, making the overall algorithm efficient.
The effectiveness of this approach lies in its ability to quickly determine potential rectangles by focusing on opposite corners. Since the sides of the rectangle are parallel to the axes, the X and Y coordinates of the corners provide a straightforward way to identify the missing corners if two opposite ones are known. This method is efficient for sparse point sets where not every combination of points forms a rectangle, thereby reducing unnecessary checks.
Step-by-Step Algorithm
-
Initialize a Set:
- Create an empty set to store all the input points for quick lookup. This set will help us check the existence of points in constant time.
-
Iterate Through All Pairs of Points:
- Use a nested loop to iterate through every pair of points from the input. These points are considered as potential opposite corners of a rectangle.
-
Check for Potential Rectangles:
- For each pair of points
(p1, p2)being considered, ensure they are not on the same horizontal or vertical line, i.e.,p1.x != p2.x && p1.y != p2.y.This check is crucial because, for a rectangle formed with sides parallel to the axes, opposite corners must have different x and y coordinates.
- For each pair of points
-
Calculate the Other Two Corners:
- For a pair of points
(p1, p2)that passes the previous check, calculate the coordinates of the other two corners of the potential rectangle. These coordinates are(p1.x, p2.y)and(p2.x, p1.y).
- For a pair of points
-
Check for the Existence of the Other Two Corners:
- Use the set created in step 1 to check if both of these calculated points exist. If both points are present in the set, it confirms the presence of a rectangle.
-
Calculate the Rectangle's Area:
- If a rectangle is confirmed, calculate its area by multiplying the absolute difference in x-coordinates by the absolute difference in y-coordinates of any two adjacent corners.
-
Track the Minimum Area:
- Maintain a variable to keep track of the minimum area of all rectangles found. Update this variable whenever a smaller area is calculated.
-
Return the Result:
- After iterating through all pairs of points, return the minimum area found. If no rectangle was formed (the minimum area was not updated), return 0.
Algorithm Walkthrough
Let's consider the Input: nums = [[0,1],[0,3],[3,1],[3,3],[4,1],[4,3]].
-
Convert Points to a Set: First, all points are added to a set for efficient lookup. This step is essential for quickly determining if the complementary points (other two corners) of a rectangle exist.
-
Iterate Over All Pairs of Points: We compare each pair of points to see if they can potentially form opposite corners of a rectangle.
- Process [0, 1]:
- Pair
[[0,1],[0,3]]: Not valid because they share the same x-coordinate. Opposite corners of a rectangle must have different x and y coordinates. - Pair
[[0,1],[3,1]]: Not valid because they share the same y-coordinate. Opposite corners of a rectangle must have different x and y coordinates. - Pair
[[0,1],[3,3]]: This is a potential pair of opposite corners. We look for points[0,3]and[3,1], which exist. Area =(3-0) * (3-1) = 6. - Pair
[[0,1],[4,1]]: Not valid because they share the same y-coordinate. - Pair
[[0,1],[4,3]]: This is a potential pair, but it essentially outlines the same rectangle as[[0,1],[3,3]]and[[4,1],[3,3]], only larger, if considering[0,3]and[4,1]as the other two points. Area =(4-0) * (3-1) = 8.
- Pair
- Process [0, 3]:
- Pair
[[0,3],[3,1]]: This is a potential pair of opposite corners. We look for points[0,1]and[3,3], which exist. Area =(3-0) * (3-1) = 6. - Pair
[[0,3],[3,3]]: Not valid because they share the same y-coordinate. - Pair
[[0,3],[4,1]]: This is a potential pair of opposite corners. We look for points[0,1]and[4,3], which exist. Area =(4-0) * (3-1) = 8. - Pair
[[0,3],[4,3]]: Not valid because they share the same y-coordinate.
- Pair
- Process [3, 1]:
- Pair
[[3,1],[3,3]]: Not valid because they share the same x-coordinate. - Pair
[[3,1],[4,1]]: Not valid because they share the same y-coordinate. - Pair
[[3,1],[4,3]]: This is a potential pair of opposite corners. We look for points[3,3]and[4,1], which exist. Area =(4-3) * (3-1) = 2.
- Pair
- Process [3, 1]:
- Pair
[[3,3],[4,1]]: This is a potential pair of opposite corners. We look for points[3,1]and[4,3], which exist. Area =(4-3) * (3-1) = 2. - Pair
[[3,3],[4,3]]: Not valid because they share the same y-coordinate.
- Pair
- Process [4, 1]:
- Pair
[[4,1],[4,3]]: Not valid because they share the same x-coordinate.
- Pair
- Determine the Smallest Area: From the valid rectangles identified, the one formed by the points
[3,1],[4,3],[3,3], and[4,1]has the smallest area of2. This is the minimum area rectangle that can be formed with the given points.
Code
Complexity Analysis
Time Complexity
The time complexity of the algorithm is primarily determined by the double loop used to iterate through all pairs of points, which gives us
Space Complexity
The space complexity is
On this page
Problem Statement
Examples
Solution
Step-by-Step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity